1. Field of Invention
The present invention relates to a method of operating a garbage collector (especially a concurrent garbage collector) in a computer system, to a computer and computer system for garbage collection, to a computer-readable storage medium and to a Virtual Machine. In a preferred embodiment, the present invention relates to grey packets: low-contention grey object sets for concurrent marking garbage collection in a highly multi-threaded environment. At a general level, the invention is applicable to run-time environments; at a more specific level it is applicable to automatic dynamic memory management.
2. Description of Related Art
In recent years, there have been developments in programming languages towards what is known as an object-oriented language. In these developments, concepts are regarded as ‘objects’, each carrying with it a set of data, or attributes, pertinent to that object, as well as information relating to so-called ‘methods’, that is functions or sub-routines, that can be performed on that object and its data. This is well known to those skilled in the art of computing and/or programming.
The advent and rapid advancement in the spread and availability of computers has led to the independent development of different types of systems, such as the IBM and IBM-compatible PC running IBM-DOS or MS-DOS or MS-Windows applications, the Apple Macintosh machines running their own Apple System operating system, or various Unix machines running their own Unix operating systems. This proliferation of independent systems has led to useful applications being available only in one format and not being capable of running on a machine for which the application was not designed.
Under such circumstances, programmers have devised software which ‘emulates’ the host computer's operating system so that a ‘foreign’ application can be made to run successfully in such a way that, as far as the user is concerned, the emulation is invisible. In other words, the user can perform all of the normal functions of say a Windows-based application on a Unix machine using a Unix-based operating system without noticing that he is doing so.
A particularly notable product of this type is that developed by Insignia Solutions of High Wycombe, GB and Santa Clara, Calif., USA and known under the name ‘SoftWindows 2.0 for Powermac’. This software enables a physical Macintosh computer to emulate a PC having an Intel 80486DX processor and 80487 maths co-processor plus memory, two hard disks, IBM-style keyboard, colour display and other features normally found on recent versions of the PC-type of computer.
Furthermore, there is an ever-increasing demand by the consumer for electronics gadgetry, communications and control systems which, like computers, have developed independently of one another and have led to incompatibility between operating systems and protocols. For example, remote-control devices for video players, tape players and CD players have similar functions, analogous to ‘play,’ ‘forward,’ ‘reverse,’ ‘pause,’ etc, but the codes for transmission between the remote control, or commander, operated by the user may not be compatible either between different types of equipment made by the same manufacturer or between the same types of equipment made by different manufacturers. There would be clear benefits of having software within the equipment which can produce for example the correct ‘play’ code based upon a ‘play’ command regardless of the specific hardware used in the equipment. Such software is commonly known as a ‘Virtual Machine.’
Other uses and applications are legion: for example, set-top boxes for decoding television transmissions, remote diagnostic equipment, in-car navigation systems and so-called ‘Personal Digital Assistants.’ Mobile telephones, for instance, can have a system upgrade downloaded to them from any service provider.
Emulation software packages tend to have certain features in common, notably that they are not general purpose but are dedicated. They are of most benefit in rapid development areas and have a distinct advantage in enabling manufacturers to cut costs. In particular, they can divorce software from the physical machine, i.e., the effect of the software in the physical machine can be altered by the emulating software without having to go into the machine's native software to implement those changes.
The specific object-oriented language used in some of the implementations described later is that known as Java (registered trade mark to Sun Microsystems Corporation). Some of the following implementations will enable Java to be used in smaller devices than is currently possible because of the improved performance and/or reduced memory footprint. Future uses projected for embedded software (virtual machines) include computers worn on the body, office equipment, household appliances, and intelligent houses and cars.
While it is recognised that there are clear advantages in the use of virtual machines, especially those using object-oriented languages, there are naturally areas where it is important and/or beneficial for some of the operations that are carried out within the system to be optimised. These may include reducing the memory requirement, increasing the speed of operation, and improving the ‘transparency’ of the system when embedded in another system. One of the principal aims of the inventions described herein is to provide a Virtual Machine which is optimised to work as quickly as possible within a memory constraint of, for example, less than 10, 5, 2 or even 1 Mbyte. Such a constraint is likely to be applicable, for example, to electronics gadgetry and other equipment where cost (or size) is a major constraint.
Reference is made herein to “memory objects”. These are typically arbitrary discrete areas of memory organised into fields, some of which may be references to other objects or even to the same object (not to be confused with the objects in object oriented programming).
For efficient use of memory in a computer system, it is important that some mechanism is in place which will allow memory to be released for reallocation so that it may be used again once its current use is expended.
Such ‘memory management’ may typically be ‘manual,’ where the program itself contains code indicating that it requires memory to perform a function and code indicating when it has finished using that memory, or ‘automatic’ where the program does not inform the computer system when it has finished with memory and instead the system itself has to implement some way of identifying and recovering expended memory. The latter is conveniently referred to as ‘garbage collection’ and relies on the computer system initiating a process in which it searches through the memory objects currently being utilised by a program. Any such objects which are encountered during the search are regarded as currently in use whilst others not encountered cannot be currently in use and may be regarded as dead and therefore available for reallocation.
In previous attempts to effect garbage collection (GC), three specific techniques have been proposed. In the first, known as ‘reference counting,’ the number of references or pointers to various memory objects are maintained and the system looks for an occasion when a reference changes to zero, thereby indicating that the object previously pointed to has become ‘free’ for reallocation. A disadvantage with this technique is that it is inefficient in multithreaded environments and is unable to detect when cyclic structures (for example, when object A refers to object B, which refers back to A again) have become garbage.
In the second technique, known as ‘copying,’ memory is divided into two sections, identified in FIG. 1A as the ‘FROM space’ 12102 and the ‘TO space’ 12104. Memory for objects is allocated at linearly increasing addresses within FROM space 12101 until it is full. At that point all work is forced to stop for GC which copies all live objects 12106 into a more compact area 12108 in the ‘TO space’ 12104. References are also changed at the same time to take account of the new locations in the ‘TO space’ 12104. The roles of the FROM and TO spaces are then reversed and new memory allocation continues but now using the TO space in the same way as the previous FROM space was used. The major disadvantages with this technique are the additional memory requirement and the down time incurred every time there is a GC routine implemented and a change over of roles between the FROM and TO spaces.
The third technique, a so-called ‘mark/sweep’ technique, involves all memory being located in one logical unit containing objects. GC is invoked when there is no region of memory in the heap large enough to satisfy an allocation request, at which point it will colour all objects “white” and trace all possible paths through references to live objects. Any objects reached by the GC are coloured “black” and regarded as live, while areas not reached remain “white” and can be regarded as dead and available for reallocation. The final stage of the technique involves a ‘sweep’ operation in which all areas marked white are released and work is allowed to continue.
In more detail, with the mark/sweep technique, as can be seen from FIG. 1B, in the marking (tracing) phase, when an object is encountered but not all of the objects it refers to have been visited, it is marked as grey and references to it are put into a data structure 12202 in the form of a memory stack termed the grey stack. (In this connection, a typical memory stack may be regarded as a memory store of variable size in which items are successively added from top to bottom so that the ‘youngest’ items are nearest the bottom of the stack. This convention is for illustrative purposes only. It makes no difference to the operation of the stack whether new items are systematically added to the top or to the bottom.) FIG. 1B also shows at 12204 a memory heap, which is the storage area for memory objects, including their coloration.
The references themselves are also investigated by looking at the first reference in the data structure. That reference is removed from the grey stack and the object it refers to is coloured “black.” Then any references 12206 in the object to other objects which have not yet been encountered by the tracing process are pushed onto the grey stack, and those objects are recolored “grey.” Each object, shown enlarged at 12208 for convenience in FIG. 1B, includes an indication 12210 of the black/white status of the reference and pointers such as 12212 to other objects in a stack. The process is repeated until the grey stack is empty. Subsequent to the tracing process there is the sweep phase in which what is black is made white and what is white is made available for future use. At the end of the garbage collection, it will be understood that the grey stack ceases to exist.
The major disadvantage with the mark/sweep (tracing) technique is the lost down time while work stops, and its greater complexity than either of the two previous techniques. Its major advantage against copying GC is that there is little or no spatial redundancy.
In so-called ‘concurrent’ environments, objects could be being manipulated whilst they are being traced. With reference to FIG. 1C, specifically a reference field “b” (12306) in an object could be updated to refer to a different reference “d” (12308). If the object A being updated (designated 12302) is “black” (that is it has been fully traced by the GC) while the new object B (designated 12304) is “white”, then there is a risk that B could be mis-identified as dead if A becomes the only route to B. This occurs because the GC has no reason to revisit A, so B will never be traced. Systems using concurrent GC use a “write barrier” to trap such situations, colouring B objects “grey” and pushing references to them onto the grey stack. Since there is only normally one grey stack for each Virtual Machine, there are likely to be contentions for usage of memory and of the grey stack when under use by GC.
Indeed, the set of grey objects is a resource shared amongst several threads of control, all of which could alter it. Hence any alteration must be policed by a locking mechanism of some kind. The grey set is used heavily during the tracing process, so there is a high probability that any attempt to gain access to the grey set will find it already in use. In addition, any overheads incurred by the locking mechanism will tend to be magnified. In other words, in concurrent GC other parts of the system can be attempting to alter objects while the GC is still tracing through methods to locate the live and dead memory locations. Special measures may need to be taken in order to prevent a live object being identified incorrectly as dead and thereby being reallocated. Corruption and/or loss of data could thereby result. A typical solution to this problem has been to use a ‘write barrier’ on all operations which could alter the contents of objects.
A further problem for GC is that space for the entire grey stack has to be allocated at the start of the GC cycle and usually has to be large enough to cope with the worst eventuality, even though it is highly unlikely that that will occur. Hence, most of the space set aside for the grey stack is wasted.